package com.chj.gaoji.class14;

import java.util.ArrayList;
import java.util.List;

public class Code13_PalindromePairs {
	public class Trie {
		Trie[] next;
		// end表示这目前这棵树是那一个索引单词的结尾
		int end;

		public Trie() {
			this.next = new Trie[26];
			this.end = -1;
		}

		// 由于待会儿用到字典树的时候，是找目标串的翻转字符串，所以插入的时候，应该是倒序插入
		public void insert(String s, int endNum) {
			char[] chars = s.toCharArray();
			Trie cur = this;
			for (int i = 0; i < chars.length; i++) {
				int index = chars[i] - 'a';
				if (cur.next[index] == null)
					cur.next[index] = new Trie();
				cur = cur.next[index];
			}
			cur.end = endNum;
		}
	}

	public List<List<Integer>> palindromePairs(String[] words) {
		// 构建字典树
		Trie trie = new Trie();
		for (int i = 0; i < words.length; i++) {
			trie.insert(reverse(words[i]), i);
		}
		List<List<Integer>> res = new ArrayList<>();
		for (int i = 0; i < words.length; i++) {
			String word = words[i];
			// 先去字典树中找整个单词的翻转作为特殊情况考虑
			int index = findWord(trie, word);
			if (index != -1 && index != i) {
				addRes(res, i, index);
			}
			// 还有一种特殊情况，我也是提交了没有通过才发现的，就是单词里有空字符串"",
			// 这意味他可以放在任何回文串的首尾
			if (isPalindrome(word)) {
				index = findWord(trie, "");
				if (index != -1 && index != i) {
					addRes(res, i, index);
					addRes(res, index, i);
				}
			}
			for (int j = 0; j < word.length(); j++) {
				String ls = word.substring(0, j + 1);
				String rs = word.substring(j + 1);
				// 先判断前半部分[0, j]是不是回文串
				if (isPalindrome(ls) && rs.length() != 0) {
					int pre = findWord(trie, rs);
					if (pre != -1 && pre != i)
						addRes(res, pre, i);
				}
				// 再判断[j + 1, end],一定要加j != word.length() - 1,要不然会和上面找整个字符串的翻转重复
				if (j != word.length() - 1 && isPalindrome(rs)) {
					int after = findWord(trie, ls);
					if (after != -1 && after != i)
						addRes(res, i, after);
				}
			}
		}
		return res;
	}

	private void addRes(List<List<Integer>> res, int i, int j) {
		List<Integer> list = new ArrayList<>();
		list.add(i);
		list.add(j);
		res.add(list);
	}

	private boolean isPalindrome(String s) {
		int i = 0;
		int j = s.length() - 1;
		char[] letters = s.toCharArray();
		while (i < j) {
			if (letters[i] != letters[j])
				return false;
			i++;
			j--;
		}
		return true;
	}

	private int findWord(Trie trie, String word) {
		Trie cur = trie;
		char[] chars = word.toCharArray();
		for (int i = 0; i < chars.length; i++) {
			int temp = chars[i] - 'a';
			if (cur.next[temp] == null)
				return -1;
			else
				cur = cur.next[temp];
		}
		return cur.end;
	}

	public static String reverse(String str) {
		char[] chs = str.toCharArray();
		int l = 0;
		int r = chs.length - 1;
		while (l < r) {
			char tmp = chs[l];
			chs[l++] = chs[r];
			chs[r--] = tmp;
		}
		return String.valueOf(chs);
	}

//	private String reverse(String word) {
//		StringBuilder sb = new StringBuilder(word);
//		return sb.reverse().toString();
//	}

	public static void main(String[] args) {
		String[] words = new String[] { "bb", "" };
		Code13_PalindromePairs cPairs = new Code13_PalindromePairs();
		List<List<Integer>> res = cPairs.palindromePairs(words);
		System.out.println(res);
	}

//	作者：ShiningShar
//	链接：https://leetcode-cn.com/problems/palindrome-pairs/solution/javazi-dian-shu-by-shiningshar/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
